#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, -1));
        dp[word1.size()][word2.size()] = 0;
        return minOPs(word1, word2, 0, 0, dp);
    }

    int minOPs(const string &word1, const string &word2, int i, int j, vector<vector<int>> &dp)
    {
        if (dp[i][j] != -1)
            return dp[i][j];
        // op insert
        int minInsert = -1;
        if (j < word2.size())
            minInsert = minOPs(word1, word2, i, j + 1, dp) + 1;
        // op delete
        int minDelete = -1;
        if (i < word1.size())
            minDelete = minOPs(word1, word2, i + 1, j, dp) + 1;
        // op replace
        int minReplace = -1;
        if (i < word1.size() && j < word2.size())
            minReplace = minOPs(word1, word2, i + 1, j + 1, dp) + (word1[i] != word2[j]);
        
        if (minInsert != -1)
            dp[i][j] = minInsert;
        if (minDelete != -1)
            dp[i][j] = dp[i][j] == -1 ? minDelete : min(dp[i][j], minDelete);
        if (minReplace != -1)
            dp[i][j] = dp[i][j] == -1 ? minReplace : min(dp[i][j], minReplace);
        return dp[i][j];
    }
};

int main()
{
    cout << "Code72" << endl;
    Solution s;
    string s1 = "r";
    string s2 = "ros";
    cout << s.minDistance(s1, s2) << endl;
    return 0;
}